let ary = [2, 5, 7, 1, 10, 14, 3, 11, 4];
// sort
// console.log(ary.sort((a, b) => a - b));

// 冒泡排序
function maopao(ary) {
    for (let i = 0; i < ary.length; i++) {
        // 自己只需跟后面的数比较，所以j从i的下一位开始
        for (let j = i + 1; j < ary.length; j++) {
            if (ary[i] > ary[j]) {
                // es6数组解构赋值交换值、或者使用一个临时变量交换值的位置
                [ary[i], ary[j]] = [ary[j], ary[i]];
            }
        }
    }
    return ary;
}
console.time('maopao');
console.log(maopao(ary));
console.timeEnd('maopao');

// 插入排序（有问题）
function charu(ary) {
    let newAry = [ary[0]];
    // 拿每一项跟newAry的每一项比较
    for (let i = 1; i < ary.length; i++) {
        const a = ary[i];
        // 因为每轮比较完之后，比较过的值会按从大到小的顺序往前排列，所以从newAry最后一项开始循环比较可以更快查到比a小的
        for (let j = newAry.length - 1; j >= 0; j--) {
            const b = ary[j];
            // 如果a比b大，则把a排在b的后面
            if (a > b) {
                newAry.splice(j + 1, 0, a);
                break;
            }
            // 如果已经比到了newAry的第一项都没有找到比a小的，则直接把a插入到newAry的第一项
            newAry.unshift(a);
        }
    }
    return newAry;
}
// console.time('charu');
// console.log(charu(ary));
// console.timeEnd('charu');

// 快速排序
function quick(ary) {
    // 递归结束
    if (ary.length <= 1) {
        return ary;
    }
    // 查找数组的中间项,并且删除中间项
    const centerIndex = Math.floor(ary.length / 2);
    const centerValue = ary.splice(centerIndex, 1)[0];
    // 使用两个数组分别接收小于中间项和大于中间项的值
    const left = [],
        right = [];
    for (let i = 0; i < ary.length; i++) {
        const element = ary[i];
        // 如果小于中间项，放左边数组，否则放右边数组
        element < centerValue ? left.push(element) : right.push(element);
    }
    // 最后再把左边的数组、中间项的值、右边数组的值拼接起来
    // 递归拿到所有按：左、中、右拼接的数组，最后形成整个数组的按从小到大排列
    return quick(left).concat(centerValue, quick(right));
}
// console.time('quick');
// console.log(quick(ary));
// console.timeEnd('quick');